

\subsection{Idea general}

La implementación del programa en \langc, se realizó usando las versiones mas conocidas de los algoritmos de ordenamiento, esto no presentó demasiados problemas, ya que son algoritmos sencillos y no es el objetivo principal del trabajo práctico. Una vez resuelto el problema en \langc, y antes de empezar a programar en \langmipsass\space se realizaron una serie de pruebas en las que se generaron esqueletos de funciones en \langc\space que luego se compilaron hacia \langmipsass\space usando el compilador, lo obtenido se usó para investigar como es la \textbf{ABI} que respeta \GCC\space en \platformguest, esto es especialmente útil a la hora de realizar el debugging con \GDB \space y al realizar el análisis de un \textit{\quotemarks{core dump}}, después de una terminación anormal del programa, el cual se puede realizar también con \GDB .\\
Se encontró que el \GCC \space reserva espacio extra en el stack, específicamente, dos palabras en el comienzo del \textbf{LTA}, espacio que es presumiblemente usado por \GDB, si se respeta esto, es posible usar el mismo para debug, en caso contrario el comportamiento no es correcto.\\ 

\subsection{Proceso de la línea de comando}

El proceso de la línea de comando se hace mediante el uso de la función \textbf{GNU} \textit{\quotemarks{getopt\_long}}, no se trata de una función \textbf{ANSI}, pero se encuentra presente en la mayoría de los *IX de código abierto, en particular las plataformas utilizadas, \platformhost\space y \platformguest, mediante el uso de la función mencionada se logra fácilmente un proceso completo de la línea de comando, con comprobación completa de errores, que incluye opciones no válidas, mal formaciones, duplicación de opciones, falta de parámetros y además sin importar el orden o la agrupación de las opciones o si se usa la versión corta o larga de las mismas.
En caso de ausencia de parámetros, estos asumen valores por omisión, los mismos son, para el caso del algoritmo de ordenamiento, usar \textbf{heapsort}, y en el caso de omitirse el archivo de salida, se usa la salida standard, no es posible omitir el o los archivos de entrada, esto se considera un error.\\

\subsection{Algoritmo \textbf{heapsort}}

\subsubsection{Heap (Montículo)}
 
Este es un ejemplo de un árbol binario completo en el cual todos sus elementos se insertan de izquierda a derecha y ningún nodo puede pasar al siguiente nivel sin antes completar el nivel anterior.\\
El montículo es un árbol binario completo, que permite implementar una cola con prioridad, y donde los elementos se almacenan de izquierda a derecha cumpliendo la propiedad de que la clave de un nodo siempre es mayor que el valor de cualquiera de sus hijos. Lo que nos asegura que la raíz del árbol, en un montículo, siempre es el elemento mayor\textbackslash menor de la estructura.

\subsubsection{Ordenamiento}

El método Heapsort es un algoritmo de ordenación basado en comparaciones de elementos que utiliza un heap para ordenarlos.\\
Se puede decir que es un algoritmo de ordenación no recursivo, no estable, con complejidad  $O\left(nlog(n)\right )$, lo cual lo hace asintoticamente óptimo .
El ordenamiento Heapsort consiste en almacenar todos los elementos del vector a ordenar en un montículo y luego extraer el nodo que queda como raíz en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima siempre, dependiendo de como se defina, contendrá el mayor o menor elemento del montículo.


\subsection{Implementación en \langmipsass}

El código se obtuvo \quotemarks{\textit{compilando}} a mano el código en \langc\space de \quotefile{heapsort.c}. Se usó solo registros temporales de \textbf{t0} a \textbf{t8} dentro del código (cuando es posible), \textbf{t9} es reservado para llamadas como es requerido para código \textbf{PIC}, se evitó usar registros callee saved, y manteniendo por tanto el stack lo mas simple y reducido posible. También se utilizan \textbf{\#defines} para poder usar los nombres de las variables originales en el código \langc\space para que el código sea mucho mas legible. Para formar el stack frame también se utilizan \textbf{\#defines} haciendo mucho mas simple el uso de un código genérico para la formación del stack en la función, en donde solo es necesario cambiar algunas constantes. Se trato de respetar la \textbf{ABI}, tal y como se vio en clase, lo cual a pesar de funcionar correctamente, causó que se produjeran anomalías durante el debugging con \GDB, como se comentó en la sección anterior.\\

\clearpage


\subsection{Stack de la función \textbf{heapsort}}

El stack se determinó posteriormente a escribir el código en \langmipsass\space, lo cual se facilitó por el uso de constantes en su definición, se trató de hacerlo lo mas simple posible al tiempo que se cumplían los requerimientos de alineación.
Como se mencionó previamente, se encontraron problemas a la hora de hacer un debug del programa en el archivo de assembly si se respetaba el stack mínimo, a pesar de funcionar correctamente, simplemente se uso la version compatible con \GDB \space hasta lograr un funcionamiento correcto y luego se modificó nuevamente para obtener el stack mínimo compatible con la \textbf{ABI} especificada en clase.


\begin{wrapfigure}{l}{0.40\textwidth}
\begin{center}
\includegraphics[width=0.35 \textwidth]{./img/stack_heapsort}
\end{center}
\caption{\label{fig:heapsortstack}\footnotesize{Stack de la función \textbf{heapsort}.}}
\end{wrapfigure}
%\vspace*{0.3cm}
El tamaño que se determinó para el stack de la función \textbf{heapsort}, fué de 14 palabras\textbackslash 56 bytes. Se reservaron (en cada caso sin contar el padding) 3 palabras para el \textbf{SRA}, ninguna para el \textbf{FRA}, 5 para el \textbf{LTA}, y dos para el \textbf{ABA}.
Como puede verse en la imagen~[\ref{fig:heapsortstack}] del stack, las palabras necesarias por padding son la  que se agrega al \textbf{SRA}, para cumplir su requisito de tamaño múltiplo de 2 palabras,en forma similar se agrega 1 palabra al \textbf{LTA} y finalmente al \textbf{ABA}, que debe ser como mínimo de 4 palabras\textbackslash 16 bytes, se le agregan 2 palabras.





\clearpage
